package leetcode.code977.SquaresofaSortedArray;

import java.util.Stack;

public class Solution1 implements ISquaresofaSortedArray {

	@Override
	public int[] sortedSquares(int[] nums) {
		Stack<Integer> s = new Stack<>();
		int[] result = new int[nums.length];
//		请你设计时间复杂度为 O(n) 的算法解决本问题
		int pointResult = 0;
		for (int num : nums) {
			int num2 = num * num;
			if (num < 0) {
				s.add(num2);
			} else {
				if (!s.empty()) {
					if (num2 < s.peek()) {
						result[pointResult] = num2;
						pointResult++;
					} else {
						while (!s.empty() && num2 > s.peek()) {
							result[pointResult] = s.pop();
							pointResult++;
						}
						result[pointResult] = num2;
						pointResult++;
					}
				} else {
					result[pointResult] = num2;
					pointResult++;
				}
			}
		}
		// 负数实在是太小了，正数都干没了，还有剩下的
		while(!s.empty()) {
			result[pointResult] = s.pop();
			pointResult++;
		}
		return result;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.myPrint1();
		so.myPrint2();
		so.myPrint3();
	}

//	输入：nums = [-4,-1,0,3,10]
//  输出：[0,1,9,16,100]
//	解释：平方后，数组变为 [16,1,0,9,100]
//	排序后，数组变为 [0,1,9,16,100]

	public void myPrint1() {
		int[] nums = { -4, -1, 0, 3, 10 };
		this.debug(nums);
	}

//	输入：nums = [-7,-3,2,3,11]
//	输出：[4,9,9,49,121]

	public void myPrint2() {
		int[] nums = { -7, -3, 2, 3, 11 };
		this.debug(nums);
	}

//	输入：nums = [-1]
//	输出：[1]

	public void myPrint3() {
		int[] nums = { -1 };
		this.debug(nums);
	}

	private void debug(int[] nums) {
		ISquaresofaSortedArray solution = new Solution1();
		int[] result = solution.sortedSquares(nums);
		for (int i : result) {
			System.out.print(i + ",");
		}
		System.out.println(" ");
	}

}
